﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Diagnostics;
namespace EvaluateMN
{
    class Program
    {

        static UInt32 v3 = Convert.ToUInt32("011011011011011011011011011011011", 2);
        static UInt32 v1 = Convert.ToUInt32("001001001001001001001001001001001", 2);
        static UInt32 v07 = Convert.ToUInt32("11000111000111000111000111000111", 2);  // 030707070707
        static void Main(string[] args)
        {
           // Console.WriteLine(o45);
            Console.ReadLine();
            Stopwatch t = new Stopwatch();
            double rst = 0;
            for (int k=0; k<=18;k++)
            {
                t.Start();
                rst = MoutN(15, 20, k, 0.9);
                t.Stop();
                Console.WriteLine($"P({k}):{rst}   {t.ElapsedMilliseconds}");
            }
            Console.WriteLine("End");
            Console.ReadLine();
        }

        // 判决1的个数 。 第一种算法. windowSize: 计算低字节的窗中1的个数
        // ----------------------------------------
        //|____|____|______________|____|____|____|
        //
        //                   [       windowSize   ]              
        static int OneCount1(UInt32 v, int windowSize)
        {
            int cnt = 0;
            v &= UInt32.MaxValue >> (32-windowSize);
            for (; v>0; cnt++)
            {
                v &= (v - 1);
            }

            return cnt;
        }

        // 判决1的个数 。 第二种算法. windowSize: 计算低字节的窗中1的个数
        // ----------------------------------------
        //|____|____|______________|____|____|____|
        //
        //                   [       windowSize   ]  
        static UInt32 OneCount2(UInt32 v, int windowSize)
        {
            v &= UInt32.MaxValue >> (32 - windowSize);
            v = (v & 0x55555555) + ((v >> 1) & 0x55555555);
            v = (v & 0x33333333) + ((v >> 2) & 0x33333333);
            v = (v & 0x0f0f0f0f) + ((v >> 4) & 0x0f0f0f0f);
            v = (v & 0x00ff00ff) + ((v >> 8) & 0x00ff00ff);
            v = (v & 0x0000ffff) + ((v >> 16) & 0x0000ffff);
            return v;
        }

        // 判决1的个数 。 第三种算法. windowSize: 计算低字节的窗中1的个数
        // ----------------------------------------
        //|____|____|______________|____|____|____|
        //
        //                   [       windowSize   ]  
        static UInt32 OneCount3(UInt32 v, int windowSize)
        {
            UInt32 tmp;
            v &= UInt32.MaxValue >> (32 - windowSize);
            tmp = v - ((v >> 1) & v3) - ((v >> 2) & v1);
            tmp = (tmp + (tmp >> 3)) & v07;
            return tmp % 63;
        }


        /// <summary>
        /// 遍历方式计算概率。
        /// </summary>
        /// <param name="M"></param>
        /// <param name="N"></param>
        /// <param name="K"></param>
        /// <param name="p"></param>
        /// <returns></returns>
        static double MoutN(int M, int N, int K, double p)
        {
            //int M = 15;  // 判决门限值
            //int N = 20;  // 观察窗大小
            //int K = 0;   // 表示第K次判决
            //double p = 0.9;   // 1次成功的概率

            double res = 0.0; // 计算结果，判决成功的概率

            //          ---------------------------------------
            //     <---|_______________________________________|---
            //
            //                           [       观察窗M       ]
            //                    [             T              ]
            int T = M + K - 1; // 总共的已经流逝的窗格个数
            UInt32 endV = UInt32.MaxValue >> (32-T);
            for (UInt32 i = 0; i <= endV; i++)
            {
                bool bCon = false;
                for (int j = 0; j <= T - N; j++)
                {
                    if (OneCount3(i >> j, N) >= M)
                    {
                        bCon = true; // 只要之前的满足条件，则退出本循环
                        break;
                    }
                }

                if (bCon)
                    continue; // 只要之前的满足条件，则继续新的循环

                if (OneCount3(i, N - 1) == M - 1)
                {
                    UInt32 cnt = OneCount3(i, T);
                    res += Math.Pow(p, cnt) * Math.Pow(1 - p, T - cnt);
                }
            }
            res *= p;
            return res;
        }

    }
}
